#include "ResultTree.hpp"

// Insertion to a result tree is inherently different from insertion to an
// fp-tree. 
// The transaction is already sorted according to decreasing item support.
// Each item is inserted one by one to the tree.
int ResultTree::insert(vector<string> * transaction, int count) { 
    string lastItem = transaction->back();
    /******************************* debug **************************
    cout << "Inside ResultTree::insert count is: " << count << 
        " and the transaction: { ";
    vector<string>::iterator dbgIt = transaction->begin(), 
        dbgEnd = transaction->end();
    for ( ; dbgIt != dbgEnd; dbgIt++) {
        cout << *dbgIt << ", ";
    }
    cout << "}" << endl;
    ******************************* debug **************************/

    hash_map<string, hash_map<int, Node *> *>::iterator it = index.find(lastItem);
    if (it == index.end()) {
        // Insert this transaction to the result tree.
        insertTransaction(transaction, count);
        return 0;
    }
    else {
        hash_map<int, Node *> * countHash = it->second;
        // Do we need to check for counts that are higher than this node's?
        // I think not because we are doing bottom to top mining, items with
        // lower or equal support are going to be inserted to the index first.
        hash_map<int, Node *>::iterator countIt = countHash->find(count);
        if (countIt == countHash->end() || 
                !isAbsorbed(countIt->second, transaction)) {
            // Either there is no second level for this item, or its support is
            // lower than our candidate. Insert this transaction too.
            insertTransaction(transaction, count);
        }
        /******************************* debug **************************
        else cout << "previous transaction not really inserted to the tree" << endl;
        ******************************* debug **************************/

    }
    // If the transaction can be absorbed by already found itemset, do nothing.
    return 0;
}

// Returns true if prefix is a subset of an already found itemset.
bool ResultTree::subItemsetPruning(Prefix & p) {
    // Items in the Prefix are in reverse f_list order.
    string lastItem = p.items.front();
    
    hash_map<string, hash_map<int, Node *> *>::iterator it = index.find(lastItem);
    if (it == index.end()) {
        // It is not a subset
        return false;
    }
    else {
        hash_map<int, Node *> * countHash = it->second;
        hash_map<int, Node *>::iterator countIt = countHash->find(p.count);
        // If it is a *proper* subset, it is not needed to be mined.
        if (countIt == countHash->end() || !isProperSubset(countIt->second, p.items)) {
            return false;
        }
        else {
            return true;
        }
    }
}

// Similar in spirit to the isAbsorbed method. The differences are that items in
// this function are sorted in the reverse f_list order and that being *proper* subset
// is mandatory.
bool ResultTree::isProperSubset(Node * node, vector<string> & items) {
    Node * current = node;

    for( ; current != NULL; ) {
        Node * temp = current;
        vector<string>::iterator it = items.begin(), end = items.end();

        bool extraItem = false;
        for ( ; ; ) {
            string item = temp->getItem();
            if (item == "root" || it == end)
                break;
            if (*it == item)
                it++;
            else 
                extraItem = true;
            temp = temp->getParent();
        }

        if (it == end && extraItem)
            return true;
        current = current->getNext();
    }
    return false;
}

// Returns 1 if a transaction can be absorbed by a branch, returns 0 if not.
// Got to check side links as well since these could be including the items too.
int ResultTree::isAbsorbed(Node * node, vector<string> * transaction) {
    Node * current = node;

    // "Node * current" is used for following side links while "Node * temp" is
    // used for following parents.
    for ( ; current != NULL; ) {
        Node * temp = current;
        vector<string>::reverse_iterator it = transaction->rbegin(), 
            end = transaction->rend();

        for ( ; ; ) { 
            string item = temp->getItem();
            if (item == "root" || it == end)
                break;
            if (*it == item)
                it++;
            temp = temp->getParent();
        }

        if (it == end)
            return 1;
        current = current->getNext();
    }
    return 0;
}

// Inserts a transaction to the result tree accordingly. Note that this
// insertion is different from normal fp-tree insertions.
int ResultTree::insertTransaction(vector<string> * transaction, int count) {
    vector<string>::iterator it = transaction->begin(), 
        end = transaction->end();
    int trSize = transaction->size();

    if (it == end)
        return 0;

    Node * current = root, * next = NULL;
    string item;
    int length = 1;

    for ( ; it != end; it++, length++) {
        item = *it;
        next = current->getNode(item);
        Node * child;
        if (next == NULL) {
            child = new Node(item, count, length);
            current->insertChild(child);
            current = child;
        }
        else {
            if (count > next->getCount()) {
                next->setCount(count);
            }
            current = next;
        }

        // If this is the last element in the transaction, insert it to the
        // index.
        if (length == trSize) 
            if (next == NULL)
                insertIndexInfo(child);
            else
                insertIndexInfo(next);
    }
    return 0;
}

// Insert the newly added node to the two level index.
int ResultTree::insertIndexInfo(Node * node) {
    int count = node->getCount();
    string item = node->getItem();
    
    // See if it is in the first level of the index.
    hash_map<string, hash_map<int, Node *> *>::iterator it = index.find(item),
        end = index.end();
    if (it == end) {
        // If not, insert to both levels.
        hash_map<int, Node *> * countsHashP = new hash_map<int, Node *>;
        (*countsHashP)[count] = node;
        index[item] = countsHashP;
        return 0;
    }

    // See if it is in the second level of the index.
    hash_map<int, Node *> * countsP = it->second;
    hash_map<int, Node *>::iterator countsIt = countsP->find(count),
        countsEnd = countsP->end();

    if (countsIt == countsEnd) {
        // If not, insert to second level.
        (*countsP)[count] = node;
    }
    else {
        // There's an entry with the same node as the last item, and has the
        // same support. ex. bc:3 and ac:3 are both inserted to the result tree.
        // We will have index such that item "c" has second level with support
        // value 3. We should insert both and link these nodes. Also talked in
        // the paper.
        Node * temp = countsIt->second;
        // Go to the end of the side links.
        for ( ; ; ) {
            if (temp->getNext() == NULL)
                break;
            else 
                temp = temp->getNext();
        }
        // Set the side link to point the new node with the same item & support.
        temp->setNext(node);
    }
    return 0;
}

// The copy assignment operator.
const ResultTree & ResultTree::operator=(const ResultTree & rhs) {
    // Check for alias.
    if (this != &rhs) {
        makeEmpty();
        const Node * rhsRoot = rhs.getRoot();
        root = new Node(rhsRoot->getItem(), rhsRoot->getCount());

        const hash_map<string, Node *> & rhsChildren = rhsRoot->getChildren();
        hash_map<string, Node *>::const_iterator rhsChildrenIt = rhsChildren.begin(),
            rhsChildrenEnd = rhsChildren.end();
        for ( ; rhsChildrenIt != rhsChildrenEnd; rhsChildrenIt++) {
            root->insertChild(duplicate(rhsChildrenIt->second));
        }
    }
    return *this;
}

// Same as the method in the Tree class. They both use Node class.
int ResultTree::makeEmpty(Node * & t) {
    if (t == NULL)
        return 0;
    
    hash_map<string, Node *> & tChildren = t->getVarChildren();
    hash_map<string, Node *>::iterator it = tChildren.begin(),
        end = tChildren.end();

    for ( ; it != end; it++) {
        Node * child = it->second;
        makeEmpty(child);
    }
    // Empty the children.
    tChildren.clear();

    delete t;
    // t must be a reference because of the below.
    t = NULL;

    return 0;
}

Node * ResultTree::duplicate(const Node * cur) {
    Node * toReturn = new Node(cur->getItem(), cur->getCount(), cur->getLength());
    // Add to two level hash index.
    insertIndexInfo(toReturn);

    const hash_map<string, Node *> & curChildren = cur->getChildren();
    hash_map<string, Node *>::const_iterator curChildrenIt = curChildren.begin(),
        curChildrenEnd = curChildren.end();

    for ( ; curChildrenIt != curChildrenEnd; curChildrenIt++) {
        toReturn->insertChild(duplicate(curChildrenIt->second));
    }
    return toReturn;
}

void ResultTree::merge(ResultTree & t) {
    Node * tRoot = t.getRoot();
    insertSubTree(root, tRoot);
    // Do we really need to reduce the item counts as well, here??
    // I think not since trees already have the global counts.
}

void ResultTree::insertSubTree(Node * fromCurrentTree, Node * fromNewTree) {
    const hash_map<string, Node *> childrenFromNew = fromNewTree->getChildren();
    hash_map<string, Node *>::const_iterator it = childrenFromNew.begin(),
        end = childrenFromNew.end();

    for ( ; it != end; it++) {
        string item = it->first;
        Node * childFromCurrent = fromCurrentTree->getNode(item);
        Node * childFromNew = it->second;
        if (childFromCurrent == NULL) {
            fromCurrentTree->insertChild(duplicate(childFromNew));
        }
        else {
            childFromCurrent->setMaxCount(childFromNew->getCount());
            insertSubTree(childFromCurrent, childFromNew);
        }
    } 
}

int ResultTree::print(string fileName) {
    hash_map<string, Node *>::const_iterator it = (root->getChildren()).begin(),
        end = (root->getChildren()).end();
    vector<string> freqItemset;

    outputStream.open(fileName.c_str(), ios::out | ios::trunc);
    if (!outputStream.is_open()) {
        cerr << "Output file could not be opened!" << endl;
        return -1;
    }

    for ( ; it != end; it++) {
        printRec(it->second, freqItemset, -1);
    }
    // Do housekeeping. ie. close the output stream.
    outputStream.close();
    return 0;
}

// "Node * node" is the node in question, vector<string> items are the current 
// items being populated, support is the support value of the parent, and will 
// be used to compare parent and child. If any of the child's support value is 
// the same as the parent's, populated items are not emitted since node's at
// lower level will have the same support and will be superset/closed set.
int ResultTree::printRec(Node * node, vector<string> items, int support) {
    hash_map<string, Node *>::const_iterator it = (node->getChildren()).begin(),
        end = (node->getChildren()).end();

    int flag = 0;

    for ( ; it != end; it++) {
        vector<string> itemsToPass = items;
        itemsToPass.push_back(node->getItem());
        flag += printRec(it->second, itemsToPass, node->getCount());
    }

    if (flag == 0) {
        // Then all the nodes have different support value (less)
        // than the parent. Thus, print the items now.
        vector<string>::iterator itemsIt = items.begin(), itemsEnd = items.end();
        for ( ; itemsIt != itemsEnd; itemsIt++) {
            outputStream << *itemsIt << " ";
        }
        outputStream << node->getItem() << " (" << node->getCount() << ")" << endl;
    }


    // Check if this is the first call from print(), and node is a child of
    // root. If so don't print anything just yet.
    if (support == -1)
        return 1;

    // Else, check the support values.
    if (support != node->getCount())
        // If the support value of a child is different from the parent, 
        // return 0.
        return 0;
    else 
        // If the support value of a child is same as the parent,
        // return 1.
        return 1;
}

